# !/usr/usuari/des python
#  -*- coding: utf-8 -*-
"""
@Author        : itgnay
@Time          : 2022/12/20 1:49
@FileName      : GCD和LCM.py
@LastEditors   : None
@Editors       : PyCharm
"""

"""辗转相除法
100 / 18 = 5 (余 10)
18 / 10= 1 (余 8)
10 / 8 = 1 (余 2)
8 / 2 = 4 (余 0)
至此，最大公约数为 2。
"""


def gcd(a, b):
    if b == 0: return a
    return gcd(b, a % b)


print(gcd(36, 21))


def lcm(a, b):
    return a * b // gcd(a, b)


print(lcm(16, 7))
